package rfc2;

import java.io.IOException;
import java.util.*;

public class RFC2 {
    public static void main(String[] args) throws IOException {
        long stime = System.currentTimeMillis();
        RFC2Game game01 = new RFC2Game();
        game01.init();

        // 运行多回合测试
        for (int i = 0; i < 50; i++) {
            game01.doTurn();
        }

        long etime = System.currentTimeMillis();
        System.out.printf("总执行时长：%d 毫秒.\n", (etime - stime));
        System.in.read();
    }
}

// A*寻路节点
class PathNode implements Comparable<PathNode> {
    int x, y;
    int gCost; // 起点到当前节点的实际代价
    int hCost; // 当前节点到终点的预估代价
    int fCost; // 总代价 f = g + h
    PathNode parent;

    public PathNode(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(PathNode other) {
        return Integer.compare(this.fCost, other.fCost);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        PathNode node = (PathNode) obj;
        return x == node.x && y == node.y;
    }

    @Override
    public int hashCode() {
        return x * 31 + y;
    }
}

// A*寻路算法实现
class AStarPathfinder {
    private static final int MAP_SIZE = 100;
    private boolean[][] obstacleMap; // 障碍物地图

    public AStarPathfinder() {
        obstacleMap = new boolean[MAP_SIZE][MAP_SIZE];
        // 初始化障碍物地图（默认无障碍物）
        for (int x = 0; x < MAP_SIZE; x++) {
            for (int y = 0; y < MAP_SIZE; y++) {
                obstacleMap[x][y] = false;
            }
        }
    }

    // 设置障碍物
    public void setObstacle(int x, int y, boolean isObstacle) {
        if (x >= 0 && x < MAP_SIZE && y >= 0 && y < MAP_SIZE) {
            obstacleMap[x][y] = isObstacle;
        }
    }

    // 计算从start到target的路径
    public List<PathNode> findPath(int startX, int startY, int targetX, int targetY) {
        PriorityQueue<PathNode> openSet = new PriorityQueue<>();
        Set<PathNode> closedSet = new HashSet<>();

        PathNode startNode = new PathNode(startX, startY);
        PathNode targetNode = new PathNode(targetX, targetY);

        openSet.add(startNode);

        while (!openSet.isEmpty()) {
            PathNode currentNode = openSet.poll();

            if (currentNode.equals(targetNode)) {
                return reconstructPath(currentNode);
            }

            closedSet.add(currentNode);

            // 获取相邻节点（上下左右）
            List<PathNode> neighbors = getNeighbors(currentNode);
            for (PathNode neighbor : neighbors) {
                if (closedSet.contains(neighbor) || obstacleMap[neighbor.x][neighbor.y]) {
                    continue;
                }

                int tentativeGCost = currentNode.gCost + 1; // 相邻节点的移动代价为1

                if (tentativeGCost < neighbor.gCost || !openSet.contains(neighbor)) {
                    neighbor.parent = currentNode;
                    neighbor.gCost = tentativeGCost;
                    neighbor.hCost = heuristic(neighbor, targetNode);
                    neighbor.fCost = neighbor.gCost + neighbor.hCost;

                    if (!openSet.contains(neighbor)) {
                        openSet.add(neighbor);
                    }
                }
            }
        }

        return null; // 没有找到路径
    }

    // 重建路径
    private List<PathNode> reconstructPath(PathNode node) {
        List<PathNode> path = new ArrayList<>();
        PathNode current = node;

        while (current != null) {
            path.add(0, current); // 从终点回溯，所以要插入到列表头部
            current = current.parent;
        }

        return path;
    }

    // 获取相邻节点
    private List<PathNode> getNeighbors(PathNode node) {
        List<PathNode> neighbors = new ArrayList<>();
        int x = node.x;
        int y = node.y;

        // 上
        if (y > 0) neighbors.add(new PathNode(x, y - 1));
        // 下
        if (y < MAP_SIZE - 1) neighbors.add(new PathNode(x, y + 1));
        // 左
        if (x > 0) neighbors.add(new PathNode(x - 1, y));
        // 右
        if (x < MAP_SIZE - 1) neighbors.add(new PathNode(x + 1, y));

        return neighbors;
    }

    // 启发式函数（曼哈顿距离）
    private int heuristic(PathNode a, PathNode b) {
        return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
    }
}

class RFC2CivilizationType {
    int m_civilization;

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        RFC2CivilizationType other = (RFC2CivilizationType) obj;
        return m_civilization == other.m_civilization;
    }
}

class RFC2City {
    int m_x;
    int m_y;
    RFC2CivilizationType eOwner;
    List<RFC2Plot> m_city_plot = new ArrayList<>();
    private RFC2Game game;

    public void setGame(RFC2Game game) {
        this.game = game;
    }

    void init(int x, int y) {
        m_x = x;
        m_y = y;
    }

    void doTurn() {
        if (game == null) {
            System.out.println("游戏实例未初始化，无法统计单位");
            return;
        }

        int unitCount = countUnitsWithinRange(3);
        game.m_count += unitCount;
    }

    private int countUnitsWithinRange(int range) {
        List<RFC2Unit> unitsInRange = game.getUnitsInRange(m_x, m_y, range);
        return unitsInRange.size();
    }
}

class RFC2Plot {
    int m_x;
    int m_y;
    RFC2CivilizationType eOwner;

    RFC2Plot(int x, int y) {
        m_x = x;
        m_y = y;
    }

    void doTurn() {
    }
}

class RFC2Unit {
    int m_x;
    int m_y;
    RFC2CivilizationType eOwner;
    private List<PathNode> currentPath; // 当前移动路径
    private AStarPathfinder pathfinder; // A*寻路器
    private RFC2Game game; // 游戏引用
    private int moveCooldown = 0; // 移动冷却

    public void setGame(RFC2Game game) {
        this.game = game;
        this.pathfinder = new AStarPathfinder();
    }

    void init(int x, int y) {
        m_x = x;
        m_y = y;
    }

    void doTurn() {
        if (game == null) return;

        // 移动冷却机制
        if (moveCooldown > 0) {
            moveCooldown--;
            return;
        }

        // 每5个回合重新计算一次路径
        if (currentPath == null || currentPath.isEmpty()) {
            RFC2Unit target = findFarthestEnemyUnit();
            if (target != null) {
                currentPath = calculatePathTo(target.m_x, target.m_y);
            }
        }

        // 沿着路径移动一步
        moveAlongPath();
    }

    // 寻找最远的非本国单位
    private RFC2Unit findFarthestEnemyUnit() {
        List<RFC2Unit> allUnits = game.getAllUnits();
        RFC2Unit farthestUnit = null;
        int maxDistance = 0;

        for (RFC2Unit unit : allUnits) {
            if (!unit.eOwner.equals(this.eOwner)) { // 非本国单位
                int distance = calculateDistance(unit.m_x, unit.m_y);
                if (distance > maxDistance) {
                    maxDistance = distance;
                    farthestUnit = unit;
                }
            }
        }

        return farthestUnit;
    }

    // 计算到目标位置的路径
    private List<PathNode> calculatePathTo(int targetX, int targetY) {
        return pathfinder.findPath(m_x, m_y, targetX, targetY);
    }

    // 沿着路径移动一步
    private void moveAlongPath() {
        if (currentPath == null || currentPath.isEmpty()) return;

        PathNode nextNode = currentPath.remove(0);
        m_x = nextNode.x;
        m_y = nextNode.y;

        // 设置移动冷却（避免单位移动过快）
        moveCooldown = 2;
    }

    // 计算到指定位置的距离
    private int calculateDistance(int x, int y) {
        return Math.abs(m_x - x) + Math.abs(m_y - y);
    }
}

class RFC2Map {
    List<RFC2Plot> m_plot = new ArrayList<>();

    void init() {
        for (int i = 0; i < 1000; i++) {
            for (int j = 0; j < 1000; j++) {
                m_plot.add(new RFC2Plot(i, j));
            }
        }
    }

    void doTurn() {
    }
}

class RFC2Team {
    void doTurn() {
    }
}

class RFC2Player {
    List<RFC2City> m_city = new ArrayList<>();
    List<RFC2Unit> m_unit = new ArrayList<>();
    RFC2CivilizationType playerID = new RFC2CivilizationType();

    void init(int iCiv) {
        playerID.m_civilization = iCiv;
        for (int i = 0; i < 100; i++) {
            RFC2City rfc2City = new RFC2City();
            rfc2City.init(i, i);
            rfc2City.eOwner = playerID;
            m_city.add(rfc2City);
        }
        for (int i = 0; i < 100; i++) {
            RFC2Unit unit = new RFC2Unit();
            unit.init(i, i);
            unit.eOwner = playerID;
            m_unit.add(unit);
        }
    }

    void doTurn() {
        for (int i = 0; i < m_city.size(); i++) {
            m_city.get(i).doTurn();
        }
        for (int i = 0; i < m_unit.size(); i++) {
            m_unit.get(i).doTurn();
        }
    }

    public List<RFC2Unit> getUnits() {
        return m_unit;
    }
}

class RFC2Game {
    RFC2Map m_map = new RFC2Map();
    List<RFC2Player> m_player = new ArrayList<>();
    long m_count;
    private int turnCount = 0; // 回合计数器

    void init() {
        for (int i = 0; i < 20; i++) {
            RFC2Player rfc2Player = new RFC2Player();
            rfc2Player.init(i);
            m_player.add(rfc2Player);

            for (RFC2City city : rfc2Player.m_city) {
                city.setGame(this);
            }

            // 设置单位的游戏引用
            for (RFC2Unit unit : rfc2Player.getUnits()) {
                unit.setGame(this);
            }
        }
        m_map.init();
    }

    void doTurn() {
        turnCount++;
        m_count = 0;

        for (int i = 0; i < m_player.size(); i++) {
            m_player.get(i).doTurn();
        }

        m_map.doTurn();
        System.out.printf("第 %d 回合完成，所有城市周围3格内的单位总数: %d\n", turnCount, m_count);
    }

    public List<RFC2Unit> getAllUnits() {
        List<RFC2Unit> allUnits = new ArrayList<>();
        for (RFC2Player player : m_player) {
            allUnits.addAll(player.getUnits());
        }
        return allUnits;
    }

    // 按区域获取单位（优化统计性能）
    public List<RFC2Unit> getUnitsInRange(int x, int y, int range) {
        List<RFC2Unit> unitsInRange = new ArrayList<>();
        int minX = Math.max(0, x - range);
        int maxX = Math.min(999, x + range);
        int minY = Math.max(0, y - range);
        int maxY = Math.min(999, y + range);

        for (RFC2Unit unit : getAllUnits()) {
            if (unit.m_x >= minX && unit.m_x <= maxX &&
                    unit.m_y >= minY && unit.m_y <= maxY) {
                unitsInRange.add(unit);
            }
        }
        return unitsInRange;
    }

    // 获取当前回合数
    public int getTurnCount() {
        return turnCount;
    }
}